<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>BFS 算法</title>
    <style>
        body {
            background: #ccc;
        }
        h1{text-align: center;}
        #map {
            width: 720px;
            margin: 0px auto;
        }

        .grid {
            float: left;
            width: 30px;
            height: 30px;
            background-color: #fff;
            margin: 1px;
            transition: .3s;
            font-size: 10px;
            color: #333;
            text-align: center;
            line-height: 30px;
        }
        .grid p{
            margin: 0;
        }

        .start {
            background-color: rgb(69, 137, 148);
        }
        .end {
            background: rgb(255, 94, 72);
        }

        .disabled {
            background: #333;
        }

        .active {
            background: rgb(250, 227, 113);
        }
    </style>
</head>
<body>
<h1>BFS 寻路算法</h1>
<div id="map">

</div>

<script>
    let oMap = document.getElementById('map');

    const maps = [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
    ]

    let start = null;
    let end = null;
    maps.forEach((n, index) => {
        var grid = document.createElement('span');
        if (n === 1) {
            grid.className = 'grid disabled';
        } else if (n === 2) {
            grid.className = 'grid end';
        } else {
            grid.className = 'grid';
        }
        grid.index = index;
        oMap.appendChild(grid);
        grid.onclick = function () {
            if( start === null && end === null ) {
                document.querySelectorAll('.grid').forEach(grid => {
                    grid.classList.remove('active');
                });
                start = index;
                this.classList.add('start');
            } else if( start !== null && end === null ) {
                this.classList.add('end');
                end = index;
                let relation = bfs(start, end);
                relation.shift();
                let grids = document.getElementsByClassName('grid');
                relation.forEach((item, i) => {
                    // grids[item.value].innerHTML = `<p>i: ${item.value}</p><p>p: ${item.parent}</p>`;
                    grids[item.value].innerHTML = `x`
                });
                let path = getPath(relation, end);
                if (path.length < 1) {
                    return;
                }
                let times = 0;
                let timmer = null;
                timmer = setInterval(() => {
                    grids[path[times]].classList.add('active');
                    grids[path[times]].innerText = times+1;
                    times++;
                    if (times === path.length) {
                        clearInterval(timmer);
                    }
                }, 30);
            } else {
                document.querySelectorAll('.grid').forEach(grid => {
                    grid.classList.remove('active', 'start', 'end');
                    grid.innerText = '';
                });
                start = index;
                end = null;
                this.classList.add('start');
            }

        }
    })

    //  获取坐标n周围可扩展路径
    function getAround(n) {
        return [n - 1, n - 22, n + 1, n + 22].filter(num => {
            //  防止最左减1后变最右
            if( (n - 1) % 22 === 21 ) return num >= 0 && num < 484 && maps[num] !== 1 && num % 22 !== 21;
            //  防止最右加1后变最左
            if( (n + 1) % 22 === 0 ) return num >= 0 && num < 484 && maps[num] !== 1 && num % 22 !== 0;
            return num >= 0 && num < 484 && maps[num] !== 1;
        });
    }

    //  通过关系队列找出路径
    function getPath(relation, end) {
        //  用来存放最终路径
        let path = [];
        //  初始化为最终目标点，然后通过改变该变量，达到不断搜索最终点到起始点之间的直接路径。
        let target = end;
        function loop() {
            //  循环关系队列，从最终点开始，根据每个节点的父节点最终找到起始点。
            for (let i = 0; i < relation.length; i++) {
                //  如果当前节点是target，继续递归搜索，直到所有节点中不存在target结束。（由于起始点没有父节点，所以最终target会变成undefined。）
                if (relation[i].value === target) {
                    //  如果当前节点的值不是最终点，就往path中压入当前节点。目的是不让最终点出现在最终的路径列表当中。
                    if (relation[i].value !== end) {
                        path.unshift(relation[i].value);
                    }
                    //  将当前target指向当前节点的父节点，然后递归继续查找。
                    target = relation[i].parent;
                    //  删除当前节点，减少下次循环次数。
                    relation.splice(i, 1);
                    loop();
                    break;
                }
            }
        }
        loop();
        return path;
    }


    //  广度优先搜索
    function bfs(start, end) {
        console.time('time');
        //  未检测或待检测列表
        let openList = [];
        //  已检测列表
        let closeList = [];
        //  出队后的检测点
        let g = null;
        //  存储已检测点的关系谱，用来获得最终可到达目标点路径顺序。
        let relation = [];

        //  第一次执行搜索，向待检测队列和关系队列压入起始点
        openList.push(start);
        relation.push({value: start});

        //  递归检测
        function loop() {
            //  如果一直递归到待检测列表为空，说明还没有找到目标点，也就是说：起始点无任何可到达目标点的路径。
            if (openList.length < 1) {
                console.log('搜索结束，无法到达');
                return;
            }
            //  从待检测队列中弹出第一个元素，并将它压入已检测队列
            g = openList.shift();
            closeList.push(g);

            //  获取本次检测点周围可覆盖点（相当于子节点）
            let around = getAround(g);

            //  循环所有子节点
            for (let i=0; i<around.length; i++) {
                //  如果当前检测点是目标点，结束递归即可。
                if (g === end) {
                    return;
                }
                if (!openList.includes(around[i]) && !closeList.includes(around[i])) {
                    //  如果子节点不存在于待检测队列和已检测队列中，将子节点压入待检测队列。通过递归检测，逐层扫描，直到全部路径扫描完。
                    openList.push(around[i]);
                    //  将扫描过的节点全部存入关系队列中，并标记每个节点的父节点。在需要的时候，可以通过关系队列中逐级找到目标点到起点的路径顺序。
                    relation.push({value: around[i], parent: g});
                }
            }
            loop();
        }
        //  执行递归检测
        loop();
        console.timeEnd('time');
        return relation;
    }


</script>
</body>
</html>